Matching markets

Economics studies how goods and services are exchanged or distributed via market.

Markets determine allocation through "prices".

But in some cases, prices may not be enough to characterize allocations, like

• College admission

• organ donation

We call these markets as matching markets.

Matching markets are typical examples of markets where there is no price

Examples are school assignment, medical match in US, dorm allocation, public housing, marriage/ dating markets.

Marriage market

We have finite sets of men and women

Men $M=\{m_1,m_2,\dots ,m_n\}$$M = \{m_1, m_2, \dots, m_n\}$, and women $W=\{w_1,\dots ,w_q\}$$W = \{w_1,\dots, w_q\}$​.

Each man has a strict preference order, $P_m$$P_m$, over the $W$$W$, and be single option $\varnothing$$\varnothing$，

Each woman has a strict preference order, $P_w$$P_w$, over $M$$M$ and $\varnothing$$\varnothing$,

For example, $P_m=\{w_1,w_2,w_3,\varnothing ,w_4\}$$P_m = \{w_1,w_2, w_3, \varnothing , w_4\}$, $w_1$$w_1$ is most preferred, $w_1,w_2,w_3$$w_1, w_2, w_3$ are acceptable, $w_4$$w_4$ is unacceptable.

And, a matching is a function $\mu$ that says who is matched with whom.

$\mu$ : $M\cup W\to M\cup W\cup \{\varnothing \}$$M \cup W \rightarrow M \cup W \cup \{\varnothing \}$

$\mu (m)$$\mu(m)$: match of man $m$$m$, and $\mu (w)$$\mu(w)$ as the match of woman $w$​.

A matching must satisfy the followings,

• For each $w\in W$$w\in W$, $\mu (w)\in M\cup \{\varnothing \}$$\mu(w) \in M \cup \{\varnothing\}$

• for each $m\in M,\mu (m)\in W\cup \{\varnothing \}$$m\in M, \mu(m) \in W \cup \{\varnothing\}$.

In marriage market, equilibrium concept is "stability" which is the conjuction of two requirements

• Individual rationality

  IR

  A matching is IR if for no $i\in M\cup W$$i\in M\cup W$, such that

  $$\begin{array}{}\text{(1)}& \varnothing P_i\mu (i)\end{array}$$

  Nobody would strictly prefer to remain single than his/her match/partner.

• No blocking pairs (NBP)

  NBP

  A pair $(m,w)$$(m,w)$ block $\mu$ if

  • $w{P}_m\mu (m)$$w P_m \mu(m)$

  • $m{P}_w\mu (w)$$mP_w \mu(w)$​

  both two sides in this pair has no better options than their match. -> NBP

• A matching $\mu$ is stable if it is IR and there is no pair man-woman that block $\mu$.

Example

Suppose we have two men and two women

$$\begin{array}{}\text{(2)}& \begin{array}{c}M=\{m_1,m_2\}\\ W=\{w_1,w_2\}\end{array}\end{array}$$

The ranking order is,

$P_{m_1}$$P_{m_1}$	$P_{m_2}$$P_{m_2}$	$P_{w_1}$$P_{w_1}$	$P_{w_2}$$P_{w_2}$
$w_1$$w_1$	$w_1$$w_1$	$m_1$$m_1$	$m_1$$m_1$
$w_2$$w_2$	$w_2$$w_2$	$m_2$$m_2$	$m_2$$m_2$
$\varnothing$$\varnothing$	$\varnothing$$\varnothing$	$\varnothing$$\varnothing$	$\varnothing$$\varnothing$

Here in this example,

$\mu (m_1)=w_2$$\mu(m_1) = w_2$,

Consider another example,

$$\begin{array}{}\text{(3)}& \begin{array}{c}M=\{m_1,m_2\}\\ W=\{w_1,w_2\}\end{array}\end{array}$$

$P_{m_1}$$P_{m_1}$	$P_{m_2}$$P_{m_2}$	$P_{w_1}$$P_{w_1}$	$P_{w_2}$$P_{w_2}$
$w_1$$w_1$	$w_2$$w_2$	$m_2$$m_2$	$m_1$$m_1$
$w_2$$w_2$	$w_1$$w_1$	$m_1$$m_1$	$m_2$$m_2$
$\varnothing$$\varnothing$	$\varnothing$$\varnothing$	$\varnothing$$\varnothing$	$\varnothing$$\varnothing$

In this example, any matching is stable.

Since being single is the least preferred option, and the number of man equals to number of woman, so in any stable matching no one remains single.

Consider the follow two possible matchings:

• $\mu (m_1)=w_1,\mu (m_2)=w_2$$\mu(m_1) = w_1, \mu(m_2) = w_2$​​,

  Since both men are matched with the top choice, no man would like to block.

• $\mu (m_1)=w_2,\mu (w_2)=w_1$$\mu(m_1) = w_2, \mu(w_2) = w_1$

  Since every women is matched with the top choices, no woman would like to block.

Both matchings are stable.

Consider another example, room mate problem, project pairing,

Now we only have one set $S=\{S_1,S_2,S_3\}$$S = \{S_1, S_2, S_3\}$

$P_{S_1}$$P_{S_1}$	$P_{S_2}$$P_{S_2}$	$P_{S_3}$$P_{S_3}$
$S_2$$S_2$	$S_3$$S_3$	$S_1$$S_1$
$S_3$$S_3$	$S_1$$S_1$	$S_2$$S_2$
$\varnothing$$\varnothing$	$\varnothing$$\varnothing$	$\varnothing$$\varnothing$

We have three potential pairs altogether, $(S_1,S_2),(S_2,S_3),(S_1,S_3)$$(S_1, S_2), (S_2, S_3), (S_1, S_3)$

Consider the first pair, $(S_1,S_2)$$(S_1, S_2)$ is blocked by $(S_2,S_3)$$(S_2,S_3)$ because the second and third person under this pair would has incentive to deviate.

Samilarly, the other pairs are blocked as well

No stable matching.

 

Theorem

For any marriage market there always exists at least one stable matching

Proof

We prove this theorem by introducing a mechanism which selects a stable matching for any market

woman proposing deferred acceptance mechanism

• Step 1:

  Every woman $w$ proposes to her most preferred man

  Every man $m$$m$ tentatively accept the most preferred acceptable proposer, and rejects the rest.

• Step 2

  Every woman $w$ proposes to her most preferred option who has not rejected her yet.

  And then man $m$$m$ that she proposes tentativey accept the most preferred acceptable proposer, and reject the rests.

• Then repeat this procedure, until no one rejects.

Outcome:

Every $w$ is matched with the most preferred option who has not rejected her.

Every $m$$m$ is matched with the woman he has tentatively accepted in the last step.

Example

Lets write down the tentative outcome in table:

Then $\mu (w_1)=m_1,\mu (w_2)=m_2,\mu (w_3)=m_3$$\mu(w_1) = m_1, \mu(w_2) = m_2, \mu(w_3)= m_3$​

For IR, no woman proposes to an unacceptable partner.. No man tentatively accepts an unacceptable partner, then the outcome of WPDA is IR.

We can show that there is no blocking pairs,

On the contrary, we assume for some market there exists a blocking pair $(m,w)$$(m,w)$ under the outcome of WPDA.

Then, $m{P}_w\mu (w)$$mP_w\mu(w)$ and $w{P}_m\mu (m)$$wP_m\mu(m)$. Since we know that $\mu$ is IR, then we know $\mu (w)$$\mu(w)$ is weakly better than $\varnothing$$\varnothing$, and $\mu (m)$$\mu(m)$ is weakly better than $\varnothing$$\varnothing$, i.e. $m{P}_w\varnothing$$m P_w \varnothing$, $w{P}_m\varnothing$$wP_m \varnothing$.

Since $w$ is matched with $\mu (w)$$\mu(w)$, under WPDA, $w$ has proposed to all men better than $\mu (w)$$\mu(w)$.

In evert further step of WPDA, every woman becomes weakly better off, which means no regret for rejection.

In some step $k$, $w$ proposed to $m$$m$,

In some step $k^{\prime }\ge k$$k^\prime \geq k$, $m$$m$ rejected $w$.

In that step $k^{\prime }$$k^\prime$, $m$$m$ tentatively accepted some $w^{\prime }$$w^\prime$ who is better than $w$. $w^{\prime }{P}_{m}w$$w^\prime P_m w$.

Since every further step $m$$m$ becomes weakly better off, $\mu (m)$$\mu(m)$ is weakly better than $w^{\prime }$$w^\prime$, $\mu (m)P_{m}w$$\mu(m)P_mw$, result in a contradiction.

Read ???